package com.sheng.leetcode.year2023.month12.day22;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2023/12/22
 * <p>
 * 1671. 得到山形数组的最少删除次数<p>
 * <p>
 * 我们定义 arr 是 山形数组 当且仅当它满足：<p>
 * arr.length >= 3<p>
 * 存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：<p>
 * arr[0] < arr[1] < ... < arr[i - 1] < arr[i]<p>
 * arr[i] > arr[i + 1] > ... > arr[arr.length - 1]<p>
 * 给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,3,1]<p>
 * 输出：0<p>
 * 解释：数组本身就是山形数组，所以我们不需要删除任何元素。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [2,1,1,5,6,2,3,1]<p>
 * 输出：3<p>
 * 解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。<p>
 * <p>
 * 提示：<p>
 * 3 <= nums.length <= 1000<p>
 * 1 <= nums[i] <= 10^9<p>
 * 题目保证 nums 删除一些元素后一定能得到山形数组。<p>
 */
public class LeetCode1671 {

    @Test
    public void test01() {
        int[] nums = {1, 3, 1};
//        int[] nums = {2, 1, 1, 5, 6, 2, 3, 1};
        System.out.println(new Solution().minimumMountainRemovals(nums));
    }
}

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] > nums[j]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] > 1 && right[i] > 1) {
                ans = Math.max(ans, left[i] + right[i] - 1);
            }
        }
        return n - ans;
    }
}
